Since the cipher is ideal, the function $\text{Enc}$ is a truly random permutation, and, in particular, for every key $k\in \mathcal{K}$ the function ${\text{Enc}}_k$ is also a truly random permutation (contrast this to the case of pseudorandom permutations, where this holds true only if the key is uniformly chosen).

The attacker is given oracle access to $(\text{Enc},\text{Dec})$ and tries to find two strings $x\ne x^{\prime }$ such that $h(x)=h(x^{\prime })$. After parsing these strings as $(k,y)$ and $(k^{\prime },y^{\prime })$, the adversary's goal reduces to finding $(k,y)$ and $(k^{\prime },y^{\prime })$ such that $\text{Enc}(k,y)\oplus y=\text{Enc}(k^{\prime },y^{\prime })\oplus y^{\prime }$.

We assume that the adversary is "smart" in the sense that they never make the same query twice (otherwise they would just be wasting their own time) and that they never query $\text{Dec}$ with a ciphertext whose plaintext they already know, lest they again waste their own time.

Consider the adversary's $i$-th query. A query to $\text{Enc}(k_i,y_i)$ reveals only the hash $h_i=h(x_i)=h(k_i||y_i)=\text{Enc}(k_i,y_i)\oplus y_i$. Similarly, a query to $\text{Dec}(k_i^{\prime },y_i^{\prime })$, will only reveal the hash $h_i=h(x_i^{\prime })=h(k_i^{\prime }||y_i^{\prime })=y_i\oplus \text{Dec}(k_i,y^{\prime })$. A collision only occurs if $h_i=h_j$ for some $i\ne j$.

Fix $i,j$ with $i>j$. When making the $i$-th query, the value of $h_j$ is already known, since it was obtained in a previous query. A collision occurs only if the adversary queries $\text{Enc}(k_i,y_i)$ and obtains $\text{Enc}(k_i,y_i)=h_j\oplus y_i$ or they query $\text{Dec}(k_i^{\prime },y_i^{\prime })$ and obtain $\text{Dec}(k_i^{\prime },y_i^{\prime })=h_j\oplus y_i^{\prime }$. Each event occurs with probability at most

$$\frac{1}{2^l-(i-1)}$$

This is true because the adversary has already made $i-1$ queries and has therefore made at most $i-1$ previous queries with the same key $k_i$. Since they are not repeating queries, there are (at most) $i-1$ fewer possible inputs the adversary can use for $y_i$. The probability of a collision at the $i$-th step is then the probability that the adversary makes an encryption query and obtains a collision or they make a decryption query and obtain a collision, i.e.

$$\mathrm{Pr}[{\text{Coll}}_{ij}]=\frac{2}{2^l-(i-1)}$$

Since $i\le q<2^{l/2}$ (comparing with the birthday attack), $i$ can be at most $2^{l/2}$ and for sufficiently large $l$, we have $2^l\gg 2^{l/2}$ which gives

$$\mathrm{Pr}[{\text{Coll}}_{ij}]\le \frac{2}{2^l}$$

The probability of a collision in $q$ queries can be expressed as

$$\mathrm{Pr}[{\text{Coll}}_q]=\mathrm{Pr}\left[\bigcup _{j<i\le q}{\text{Coll}}_{ij}\right]$$

By the union bound, we obtain

$$\mathrm{Pr}[{\text{Coll}}_q]\le \sum _{j<i\le q}\mathrm{Pr}[{\text{Coll}}_{ij}]$$

The number of distinct pairs $i,j$ which satisfy $j<i\le q$ is exactly $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ which is upper bounded by $\frac{q^2}{2}$. Ultimately, we have that

$$\mathrm{Pr}[{\text{Coll}}_q]\le \sum _{j<i\le q}\mathrm{Pr}[{\text{Coll}}_{ij}]\le \frac{q^2}{2}\mathrm{Pr}[{\text{Coll}}_{ij}]=\frac{q^2}{2^l}$$